#include "trie.h"

Trie::Trie() { root = NULL; }

//Trie中的查找操作private写的
Trienode<string>* Trie::search(Trienode<string>* u, string key, int d) {
    if(u == nullptr) return nullptr;
    if(d == key.size()) return u;
    char c = key[d];
    return search(u->next[c], key, d  +1);
}


//Trie中的插入操作 private
Trienode<string>* Trie::insert(Trienode<string>* u, string key, int d, string value) {
    if(u == nullptr) u = new Trienode<string>();
    if(d == key.size()) {
        u->value = value;
        return u;
    }
    char c = key[d];
    u->next[c] = insert(u->next[c], key, d + 1, value);
    return u;
}

//Trie中的查找操作
string Trie::search(string key) {
     Trienode<string>* res = search(root, key, 0);
     if(res == nullptr) return "未找到该单词";
     return res->value;
}

//Trie中的插入操作
void Trie::insert(string key, string value) {
  root = insert(root, key, 0, value);
}

//清理内存
void Trie::clear(Trienode<string>* u) {
    for(int i = 0; i < 300; i++)
       if(u->next[i]) clear(u->next[i]);
         delete u;
}

//析构函数
Trie::~Trie() {
    clear(root);
}

void Trie::deleteNode(Trienode<string>* &u, string key, int d) {
    if(u == nullptr) return ;
    if(d == key.size()) {
        u->value = "未找到该单词";
        return ;
    }
    char c = key[d];
    deleteNode(u->next[c], key, d + 1);
}

void Trie::deleteNode(string key) {
    deleteNode(root, key, 0);
}

